package a.codetop.笔试框架.DP;

public class 编辑距离 {

    //————————(增改)删s1去凑tar————分组合总数+,最少操作次数min——————————————————————————————————————————————————

    /*
        删s1凑tar_所有组合总数【子序列个数】
    */
    public int 删s1凑tar_所有组合总数(String tar,String s1){
        int n1=tar.length(),n2=s1.length();
        int[][] dp = new int[n1+1][n2+1];
        //
        for(int j=0;j<=n2;j++)dp[0][j]=1;//tar="",算一个子集（子集含[]的）
        //
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(tar.charAt(i-1)==s1.charAt(j-1))dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
                else dp[i][j]=dp[i][j-1];
            }
        }
        //
        return dp[n1][n2];
    }

    /*
        增删改s1凑tar_最少操作次数
    */
    public int 增删改s1凑tar_最少操作次数(String tar,String s1){
        int n1=tar.length(),n2=s1.length();
        int[][] dp=new int[n1+1][n2+1];//注意：因为n1+1所以下面i-1和j-1比哦
        //
        for(int j=0;j<=n2;j++)dp[0][j]=j;
        for(int i=0;i<=n1;i++)dp[i][0]=i;
        //
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(tar.charAt(i-1)==s1.charAt(j-1))dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min3(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
            }
        }
        //
        return dp[n1][n2];
    }
    public int min3(int a,int b,int c){
        int r1=Math.min(a,b);
        return Math.min(c,r1);
    }
    //————————————————————————————————————————————————————————————————————————————————



    //——————s1,s2两个串都可以删——————————————————————————————————————————————————————————————————————————

    /*
        s1,s2两方任意删至变为一样_最少操作次数
    */
    public int s1和s2两方任意删至变为一样_最少操作次数(String s1,String s2){
        int len=最长xx.最长公共子序列(s1,s2);
        return s1.length()-len+s2.length()-len;
    }

    //————————————————————————————————————————————————————————————————————————————————

}
